//
//  Combine.swift
//  LeetCodeDemo
//
//  Created by 杨冬武 on 2022/6/17.
//

import Foundation

/*
 77. 组合
 
 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

 你可以按 任何顺序 返回答案。
 
 */

class Combine {
    
    var ans = [[Int]]()
    var temp = [Int]()
    var n = 0
    var k = 0
    
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        self.n = n
        self.k = k
        dfs(1)
        return ans
    }
    
    func dfs(_ cur: Int) {
        if temp.count + n - cur + 1 < k {
            return
        }
        if temp.count == k {
            ans.append(temp)
            return
        }
        if cur > n {
            return
        }
        temp.append(cur)
        dfs(cur + 1)
        _ = temp.popLast()
        dfs(cur + 1)
    }
    
    
}
